package ViolenceRecursive;

/**
 * 给女主播刷礼物，如何用最少的钱刷到固定的人气值
 *
 * @author Liaorun
 */
public class KiKi {

    public static void main(String[] args) {
        System.out.println(minCoins1(2, 2, 2, 1, 10));
    }

    public static int minCoins1(int add, int times, int del, int start, int end) {
        if (start > end) {
            return -1;
        }

        return process(0, end, add, times, del, start, end * 2, ((end - start) / 2) * add);
    }

    /**
     * @param preMoney  之前已经花了多少钱
     * @param end       目标人气值
     * @param add       增加人气的方式需要的钱
     * @param times     加倍人气的方式需要的钱
     * @param del       减少人气的方式需要的钱
     * @param start     当前的人气
     * @param limitAim  人气超过这个值就不在递归尝试
     * @param limitCoin 花费价格超过这个值就不在递归尝试
     * @return Integer.MAX_VALUE -> 无解; another int -> 需要的最少价格
     */
    private static int process(int preMoney, int end, int add, int times, int del, int start, int limitAim, int limitCoin) {

        // 花费的钱多余最差的方式，不用在尝试了
        if (preMoney > limitCoin) {
            return Integer.MAX_VALUE;
        }

        // 人气小于0，不用在尝试了
        if (start < 0) {
            return Integer.MAX_VALUE;
        }

        if (start > limitAim) {
            return Integer.MAX_VALUE;
        }

        if (end == start) {
            return preMoney;
        }

        int min = Integer.MAX_VALUE;
        // 尝试让人气+2的方式
        int p1 = process(preMoney + add, end, add, times, del, start + 2, limitAim, limitCoin);

        if (p1 != Integer.MAX_VALUE) {
            min = p1;
        }
        // 让人气 -2的方式
        int p2 = process(preMoney + del, end, add, times, del, start - 2, limitAim, limitCoin);

        if (p2 != Integer.MAX_VALUE) {
            min = Math.min(min, p2);
        }

        int p3 = process(preMoney + times, end, add, times, del, start * 2, limitAim, limitCoin);

        if (p3 != Integer.MAX_VALUE) {
            min = Math.min(min, p3);
        }

        return min;
    }

    /**
     * 错误解法： base case 结束递归的情况太苛刻，达不到，进入死循环
     *
     * @param x   一种道具花费的钱
     * @param y   一种道具花费的钱
     * @param z   一种道具花费的钱
     * @param end 目标人气
     * @param cur 当前人气
     * @return
     */
    public static int func(int x, int y, int z, int end, int cur) {
        if (cur == end) {
            return 0;
        }

        int p1 = process(x, y, z, end, cur + 2) + x;
        int p2 = process(x, y, z, end, cur * 2) + y;
        int p3 = process(x, y, z, end, cur - 2) - z;

        return Math.min(p1, Math.min(p2, p3));
    }

    private static int process(int x, int y, int z, int end, int i) {
        return 0;
    }
}
